package org.gpf;

import java.util.Arrays;

/**
 * 排序工具类
 * 
 * @author gaopengfei
 * @date 2015-4-13 上午8:30:10
 */
public class SortUtil {
	
	/**
	 * 将构造私有化，防止其产生实例化对象
	 */
	public SortUtil() {
		
	}

	/**
	 * 选择排序
	 * @param number
	 */
	public static void selectionSort(int[] number) {

		if (number.length <= 1 || number == null) {
			return;
		}

		for (int i = 0; i < number.length - 1; i++) {
			for (int j = i + 1; j < number.length; j++) {
				if (number[j] < number[i]) {
					int temp = number[i];
					number[i] = number[j];
					number[j] = temp;
				}
			}
		}

	}

	/**
	 * 冒泡排序
	 * @param number
	 */
	public static void bubbleSort(int[] number) {

		if (number.length <= 1 || number == null) {
			return;
		}
		for (int i = 0; i < number.length; i++) {
			for (int j = 0; j < number.length - 1; j++) {
				if (number[j + 1] < number[j]) {
					int temp = number[j];
					number[j] = number[j + 1];
					number[j + 1] = temp;
				}
			}

		}

	}
	
	/**
	 * 冒泡排序的改进
	 * @param number
	 * @param n 数组长度
	 */
	public static void bubbleSort(int[]number,int n){
		
		for(boolean sorted = false;sorted =!sorted;n--){ // 逐趟扫描交换，直到数组有序
			for(int i = 1;i < n;i++){ 					// 从做到右，逐对检查A[0,n)内各相邻元素
				if(number[i-1] > number[i]){            // 如果逆序则交换
					number[i] = number[i] ^ number[i-1];
					number[i-1] = number[i] ^ number[i-1];
					number[i] = number[i] ^ number[i-1];
					sorted = false;                    // 清除有序状态
				}
			}
		}
	}

	/**
	 * 插入排序
	 * @param number
	 */
	public static void insertSort(int[] number) {

		if (number.length <= 1 || number == null) {
			return;
		}
		for (int i = 1; i < number.length; i++) {
			int temp = number[i]; 						// 待插入元素
			int j;
			for (j = i - 1; j >= 0; j--) {
				if (number[j] > temp) {
					number[j + 1] = number[j]; 			// 有序数组中大于待插入元素的向后移动
				} else {
					break; 								// 如果比有序数组中的最后一个元素大，直接跳出
				}
			}
			number[j + 1] = temp;
		}

	}

	
	public static void main(String[] args) {
		
		int[] arr = {2,3,5,1,4,9,-2,2};
		bubbleSort(arr, arr.length);
		System.out.println(Arrays.toString(arr));
	}
	
}
